Interval list intersections

Time: O(M+N); Space: O(1); medium

Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

(Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b. The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].)

Example 1:

Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]

Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Constraints:

  • 0 <= len(A) < 1000

  • 0 <= len(B) < 1000

  • 0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9

[12]:

class Interval(object):
    def __init__(self, s=0, e=0):
        self.start = s
        self.end = e

1. Merge Intervals

Intuition

In an interval [a, b], call b the “endpoint”.

Among the given intervals, consider the interval A[0] with the smallest endpoint. (Without loss of generality, this interval occurs in array A.)

Then, among the intervals in array B, A[0] can only intersect one such interval in array B. (If two intervals in B intersect A[0], then they both share the endpoint of A[0] – but intervals in B are disjoint, which is a contradiction.)

Algorithm

If A[0] has the smallest endpoint, it can only intersect B[0]. After, we can discard A[0] since it cannot intersect anything else.

Similarly, if B[0] has the smallest endpoint, it can only intersect A[0], and we can discard B[0] after since it cannot intersect anything else.

We use two pointers, i and j, to virtually manage “discarding” A[0] or B[0] repeatedly.

[13]:

class Solution1(object):
    """
    Time: O(M+N), where M, N are the lengths of A and B respectively.
    Space: O(M+N), the maximum size of the answer.
    """
    def intervalIntersection(self, A, B):
        """
        :type A: List[Interval]
        :type B: List[Interval]
        :rtype: List[Interval]
        """
        result = []
        i, j = 0, 0

        while i < len(A) and j < len(B):

            # Let's check if A[i] intersects B[j].
            # left - the startpoint of the intersection
            # right - the endpoint of the intersection
            left = max(A[i].start, B[j].start)
            right = min(A[i].end, B[j].end)

             # Remove the interval with the smallest endpoint
            if left <= right:
                result.append(Interval(left, right))
            if A[i].end < B[j].end:
                i += 1
            else:
                j += 1

        return result

[14]:

s = Solution1()

A = [Interval(0,2), Interval(5,10), Interval(13,23), Interval(24,25)]
B = [Interval(1,5), Interval(8,12), Interval(15,24), Interval(25,26)]
res = s.intervalIntersection(A, B)
exp = [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
for i in range(len(res)):
    assert res[i].start == exp[i][0]
    assert res[i].end == exp[i][1]